//<p>给定一个二叉树的 <strong>根节点</strong> <code>root</code>，请找出该二叉树的 <strong>最底层 最左边 </strong>节点的值。</p>
//
//<p>假设二叉树中至少有一个节点。</p>
//
//<p> </p>
//
//<p><strong>示例 1:</strong></p>
//
//<p><img src="https://assets.leetcode.com/uploads/2020/12/14/tree1.jpg" style="width: 182px; " /></p>
//
//<pre>
//<strong>输入: </strong>root = [2,1,3]
//<strong>输出: </strong>1
//</pre>
//
//<p><strong>示例 2:</strong></p>
//
//<p><img src="https://assets.leetcode.com/uploads/2020/12/14/tree2.jpg" style="width: 242px; " /><strong> </strong></p>
//
//<pre>
//<strong>输入: </strong>[1,2,3,4,null,5,6,null,null,7]
//<strong>输出: </strong>7
//</pre>
//
//<p> </p>
//
//<p><strong>提示:</strong></p>
//
//<ul>
//	<li>二叉树的节点个数的范围是 <code>[1,10<sup>4</sup>]</code></li>
//	<li><meta charset="UTF-8" /><code>-2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1</code> </li>
//</ul>
//<div><div>Related Topics</div><div><li>树</li><li>深度优先搜索</li><li>广度优先搜索</li><li>二叉树</li></div></div><br><div><li>👍 237</li><li>👎 0</li></div>

package leetcode.editor.cn;

public class _513_FindBottomLeftTreeValue {
    public static void main(String[] args) {
        Solution solution = new _513_FindBottomLeftTreeValue().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        int maxLeftVal;
        int maxLevel = -1;
        public int findBottomLeftValue(TreeNode root) {
            findBottom(root, 0);
            return maxLeftVal;
        }

        private void findBottom(TreeNode root, int level) {
            if (root.left==null&& root.right==null){
                if (maxLevel<level){
                    maxLevel = level;
                    maxLeftVal=root.val;
                }
                return;
            }
            if (root.left!=null) {
                findBottom(root.left, level+1);
            }
            if (root.right!=null) {
                findBottom(root.right, level+1);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}